﻿#region File Info
// File: EbnfParser.cs
// Product: Ebnf Visualizer
// Types: 
//    class EbnfParser
//    enum EbnfSymbolType
//    class EbnfSymbol
// License:
// Copyright (C) 2010 Daniel Kuschny (http://www.coderline.net)
//
// This file is part of Ebnf Visualizer.
//
// Ebnf Visualizer is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Ebnf Visualizer is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Ebnf Visualizer. If not, see <http://www.gnu.org/licenses/>.
#endregion

using System;
using System.Collections.Generic;
using System.Drawing.Drawing2D;
using System.Text.RegularExpressions;
using System.Windows.Forms;
using System.Xml;
using System.Drawing;
using System.Drawing.Text;

namespace EbnfVisualizer
{
    /// <summary>
    /// Dieser Parser verarbeitet EBFN Grammatiken und ermöglicht ein berechnen eines
    /// Diagramms.
    /// </summary>
    /// <remarks>
    /// Dieser Code basiert auf dem Quellcode von:
    ///     Vincent Tscherter, tscherter@karmin.ch, Solothurn, 2009-01-18
    ///     http://karmin.ch/ebnf/index (22.03.2010)
    /// Version Log:
    ///     2009-01-18 version 0.1 first release - Vincent Tscherter
    ///     2009-01-02 version 0.2 - Vincent Tscherter
    ///         - title und comment literal added
    ///         - ";" als terminator-symbol added
    ///     2010-03-22 version 1.0 C# Version - Daniel Kuschny
    /// </remarks>
    public class EbnfParser
    {
        #region Konstanten

        /// <summary>
        /// Standard Schriftart für Texte
        /// </summary>
        private static readonly Font DefaultFont = new Font("Lucida Console", 12, FontStyle.Bold, GraphicsUnit.Pixel);

        /// <summary>
        /// Standard Grammatik bei Fehlern
        /// </summary>
        private const string DefaultString = "Syntax     = { Regel } ." +
                                             "Regel      = Identifier \"=\" Ausdruck ( \".\" | \";\" ) ." +
                                             "Ausdruck   = Term { \"|\" Term } ." +
                                             "Term       = Faktor { Faktor } ." +
                                             "Faktor     = Zeichenkette" +
                                             "         | Literal" +
                                             "         | \"[\" Ausdruck \"]\"" +
                                             "         | \"(\" Ausdruck \")\"" +
                                             "         | \"{\" Ausdruck \"}\" ." +
                                             "Literal    = \"'\" Zeichenkette \"'\"" +
                                             "         | '\"' Zeichenkette '\"' ." +
                                             "Zeichenkette = Zeichen { Zeichen } .";
        /// <summary>
        /// Diese Konstante wird für eine Reihe von Zeichenoperationen verwendet.
        /// </summary>
        private const int DrawingUnit = 10;

        /// <summary>
        /// Eine Liste mit Patterndefinitionen um Symbole zu erkennen
        /// </summary>
        private static readonly Dictionary<EbnfSymbolType, string> SymbolPatterns;

        /// <summary>
        /// Initialisiert die <see cref="EbnfParser"/> Klasse.
        /// </summary>
        static EbnfParser()
        {
            // Lexikalische Einheiten (Regex)
            SymbolPatterns = new Dictionary<EbnfSymbolType, string>
                           {
                               {EbnfSymbolType.Operator, @"[={}()|.;[\]]"},
                               {EbnfSymbolType.Literal, "\"[^\"]*\""},
                               {EbnfSymbolType.Literal2, "'[^']*'"},
                               {EbnfSymbolType.Identifier, "[a-zA-Z0-9_-]+"},
                               {EbnfSymbolType.WhiteSpace, "\\s+"}
                           };
        }
        #endregion

        #region Parser Typen

        /// <summary>
        /// Diese Enumeration listed alle Symboltypen auf.
        /// </summary>
        private enum EbnfSymbolType
        {
            Operator,
            Literal,
            Literal2,
            WhiteSpace,
            Identifier
        }

        /// <summary>
        /// Stellt ein Symbol einer Grammatik dar.
        /// </summary>
        private class EbnfSymbol
        {
            /// <summary>
            /// Ruft den Symboltyp ab.
            /// </summary>
            public EbnfSymbolType Type { get; private set; }

            /// <summary>
            /// Ruft die Position des Symbols im Ausgangstext ab.
            /// </summary>
            public int Position { get; private set; }

            /// <summary>
            /// Ruft den Inhaltstext des Symbols ab. 
            /// </summary>
            public string Value { get; private set; }

            /// <summary>
            /// Initialisiert eine neue Instanz der <see cref="EbnfSymbol"/> Klasse.
            /// </summary>
            /// <param name="type">Der Symboltyp.</param>
            /// <param name="position">Die Symbolposition im Ausgangstext.</param>
            /// <param name="value">Der Inhaltstext des Symbols</param>
            public EbnfSymbol(EbnfSymbolType type, int position, string value)
            {
                Type = type;
                Position = position;
                Value = value;
            }
        }

        #endregion

        #region Felder

        // Ablage für Regeln
        private readonly Dictionary<string, XmlElement> _ruleBackStore = new Dictionary<string, XmlElement>();
        private readonly List<string> _rules = new List<string>();

        private XmlDocument _syntaxTree;

        #endregion

        #region Eigenschaften

        /// <summary>
        /// Ruft die aktuell angezeigte Regel ab.
        /// </summary>
        /// <seealso cref="ShowRule"/>
        public string CurrentRule { get; private set; }

        /// <summary>
        /// Ruft eine Liste der verfügbaren Regeln ab.
        /// </summary>
        /// <remarks>
        /// Diese Liste ist nicht beschreibbar.
        /// </remarks>
        public IList<string> Rules
        {
            get
            {
                return _rules.AsReadOnly();
            }
        }

        /// <summary>
        /// Ruft den Titel des Bildes ab oder legt diesen fest.
        /// </summary>
        public string Title { get; set; }

        /// <summary>
        /// Ruft den aktuell vorliegenen Fehler ab. (oder null wenn kein Fehler vorhanden ist)
        /// </summary>
        public EbnfException Error { get; private set; }

        #endregion

        #region User Api
        /// <summary>
        /// Verarbeitet eine EBNF Grammatik und berechnet deren grafische Darstellung.
        /// </summary>
        /// <param name="input">Die EBNF Grammatik</param>
        /// <returns>Das grafische Diagramm welches aus der Grammatik resultiert.</returns>
        public Image Parse(string input)
        {
            try
            {
                try
                {
                    // Keine Eingabe abbrechen 
                    if (string.IsNullOrEmpty(input))
                    {
                        throw new Exception("Keine Grammatik eingegeben! Unterstützte EBNF:");
                    }
                    LexicalAnalysis(input);
                    SyntaxAnalysis();
                    Error = null;
                    return ShowAsAvailable();
                }
                catch (EbnfException)
                {
                    throw;
                }
                catch (Exception e)
                {// Exception die keine Ebnf Exceptions sind verpacken
                    throw new EbnfException(e.Message, 0, e);
                }
            }
            catch (EbnfException ex)
            {
                Error = ex;
                input = DefaultString;
                LexicalAnalysis(input);
                SyntaxAnalysis();
                return ShowAsAvailable();
            }
        }

        /// <summary>
        /// Rendert das Bild entsprechend der verfügbaren Daten
        /// </summary>
        /// <returns>
        /// Ein Bild welches alle Regeln beinhaltet sofern <see cref="CurrentRule"/> nicht existiert,
        /// andernfalls ein Bild mit nur der aktuellen Regel.
        /// </returns>
        private Image ShowAsAvailable()
        {
            if (!string.IsNullOrEmpty(CurrentRule) && _ruleBackStore.ContainsKey(CurrentRule))
            {
                return ShowRule(CurrentRule);
            }
            return ShowAllRules();
        }

        /// <summary>
        /// Rendert ein Bild mit der gegebenen Regel.
        /// </summary>
        /// <param name="rule">Die Regel welche im Bild angezeigt werden soll.</param>
        /// <returns>Das Bild mit der gewünschten Regel oder null wenn die gegebene Regel nicht existiert</returns>
        public Image ShowRule(string rule)
        {
            if (_ruleBackStore.ContainsKey(rule))
            {
                CurrentRule = rule;
                // Neuen Baum erzeugen
                XmlElement root = (XmlElement)_syntaxTree.DocumentElement.CloneNode(false);
                XmlElement ruleNode = (XmlElement)_ruleBackStore[rule].CloneNode(true);
                root.AppendChild(ruleNode);

                return SemanticEvaluation(root, true);
            }
            return null;
        }

        /// <summary>
        /// Rendert ein Bild mit allen verfügbaren Regeln.
        /// </summary>
        /// <returns>Ein Bild mit allen verfügbaren Regeln.</returns>
        public Image ShowAllRules()
        {
            if (_syntaxTree == null)
            {
                return Parse("");
            }
            CurrentRule = null;
            return SemanticEvaluation(_syntaxTree.DocumentElement, true);
        } 
        #endregion

        #region 1. Lexikalische Analyse

        private readonly List<EbnfSymbol> _symbols = new List<EbnfSymbol>();

        /// <summary>
        /// Führt die lexikalische Analyse einer EBNF Grammatik durch.
        /// </summary>
        /// <param name="input">Die EBNF Grammatik.</param>
        /// <returns>Eine Symbol-Liste der EBNF Grammatik.</returns>
        private void LexicalAnalysis(string input)
        {
            int i = 0;
            int n = input.Length;
            int m = SymbolPatterns.Count;
            _symbols.Clear();

            // Alle Zeichen durchlaufen
            while (i < n)
            {
                // Versuchen das Symbol anhand Regulärer Ausdrücke zu identifizieren
                int j = 0;
                MatchCollection matches = null;
                while (j < m && matches == null)
                {
                    string s = input.Substring(i);
                    string regex = "^" + SymbolPatterns[(EbnfSymbolType)j];
                    matches = Regex.Matches(s, regex);
                    if (matches.Count == 0)
                    {
                        j++;
                        matches = null;
                    }
                }

                // Alle Symbole bis auf WhiteSpaces aufnehmen 
                if (matches != null)
                {
                    if ((EbnfSymbolType)j != EbnfSymbolType.WhiteSpace)
                    {
                        _symbols.Add(new EbnfSymbol((EbnfSymbolType)j, i, matches[0].Value));
                    }
                    i += matches[0].Length;
                }
                else
                {
                    throw new LexicalException("Unbekanntes Symbol an Position: " + i, i);
                }
            }
        }

        #endregion

        #region 2. Syntaktische Analyse

        private int _currentSymbolIndex;


        /// <summary>
        /// Ruft das aktuelle Symbol ab auf welchem sich der Analysator befindet.
        /// </summary>
        private EbnfSymbol CurrentSymbol
        {
            get
            {
                if (_currentSymbolIndex >= _symbols.Count)
                {
                    int pos = 0;
                    if (_currentSymbolIndex > 0)
                        pos = _symbols[_currentSymbolIndex - 1].Position + _symbols[_currentSymbolIndex - 1].Value.Length - 1;
                    return new EbnfSymbol(EbnfSymbolType.WhiteSpace, pos, "");
                }
                return _symbols[_currentSymbolIndex];
            }
        }

        /// <summary>
        /// Ruft das aktuelle Symbol ab auf welchem sich der Analysator befindet und 
        /// bewegt danach den Analysator ein Symbol weiter. 
        /// </summary>
        private EbnfSymbol NextSymbol
        {
            get
            {
                // Beim letzten Token einen Fehler token zurückgeben
                if (_currentSymbolIndex >= _symbols.Count)
                {
                    int pos = 0;
                    if (_currentSymbolIndex > 0)
                        pos = _symbols[_currentSymbolIndex - 1].Position + _symbols[_currentSymbolIndex - 1].Value.Length - 1;
                    return new EbnfSymbol(EbnfSymbolType.WhiteSpace, pos, "");
                }
                return _symbols[_currentSymbolIndex++];
            }
        }

        /// <summary>
        /// Analysiert die Syntax einer EBNF Grammatik anhand der gegebenen Symbol-Liste.
        /// </summary>
        /// <returns>Eine Syntax-Baum für den semantischen Auswerter</returns>
        private void SyntaxAnalysis()
        {
            // Syntax Baum vorbereiten
            _syntaxTree = new XmlDocument();
            XmlElement syntax = _syntaxTree.CreateElement("Syntax");
            _syntaxTree.AppendChild(syntax);

            // Alte Regeln löschen
            _ruleBackStore.Clear();
            _rules.Clear();

            // Neue Regeln durchlaufen und in Syntaxbaum eingliedern
            _currentSymbolIndex = 0;
            while (_currentSymbolIndex < _symbols.Count && CurrentSymbol.Type == EbnfSymbolType.Identifier)
            {
                XmlElement rule = ParseEbnfRule(_syntaxTree);
                syntax.AppendChild(rule);

                // Verfügbare Regeln zwischenspeichern
                string ruleName = rule.GetAttribute("name");
                if (ruleName != "")
                {
                    _ruleBackStore.Add(ruleName, rule);
                    _rules.Add(ruleName);
                }
            }

            return;
        }

        /// <summary>
        /// Parst eine EBNF Regel für den Syntax-Baum.
        /// </summary>
        /// <param name="tree">Der Syntax-Baum.</param>
        /// <returns>
        /// Der Knoten welcher in den Syntax-Baum eingegliedert werden muss
        /// </returns>
        private XmlElement ParseEbnfRule(XmlDocument tree)
        {
            // Bezeichner zu Beginn?
            EbnfSymbol symbol = NextSymbol;
            if (symbol.Type != EbnfSymbolType.Identifier)
                throw new SyntaxException("Bezeichner für Regeldefinition erwartet an Position: " + symbol.Position, symbol.Position);

            // Knoten erzeugen
            XmlElement rule = tree.CreateElement("Rule");
            rule.SetAttribute("name", symbol.Value);

            // = nach Regelbezeichner
            symbol = NextSymbol;
            if (!IsSymbol(symbol, EbnfSymbolType.Operator, "="))
                throw new SyntaxException("'=' nach Regelbezeichner erwartet an Position: " + symbol.Position, symbol.Position);

            // Regeldefinition in Syntaxbaum laden
            rule.AppendChild(ParseEbnfExpression(tree));
            symbol = NextSymbol;

            // Satzende 
            if (!IsSymbol(symbol, EbnfSymbolType.Operator, ".") && !IsSymbol(symbol, EbnfSymbolType.Operator, ";"))
                throw new SyntaxException("'.' oder ';' erwartet an Position: " + symbol.Position, symbol.Position);

            return rule;
        }

        /// <summary>
        /// Parst einen EBNF Ausdruck für den Syntax-Baum.
        /// </summary>
        /// <param name="tree">Der Syntax-Baum.</param>
        /// <returns>Der Knoten welcher in den Syntax-Baum eingegliedert werden muss</returns>
        private XmlElement ParseEbnfExpression(XmlDocument tree)
        {
            XmlElement expression = tree.CreateElement("Expression");

            // Pflicht-Term lesen
            expression.AppendChild(ParseEbnfTerm(tree));

            // Nach weiteren Termen prüfen
            EbnfSymbol symbol = CurrentSymbol;
            bool multipleTerms = false;
            // | verknüpfungen?
            while (IsSymbol(symbol, EbnfSymbolType.Operator, "|"))
            {
                _currentSymbolIndex++;
                expression.AppendChild(ParseEbnfTerm(tree));
                symbol = CurrentSymbol;
                multipleTerms = true;
            }

            // Entweder den Ausdruck mit mehreren Termen oder nur den Einzelterm anhängen. 
            return multipleTerms ? expression : (XmlElement)expression.RemoveChild(expression.FirstChild);
        }

        /// <summary>
        /// Parst einen EBNF Term für den Syntax-Baum.
        /// </summary>
        /// <param name="tree">Der Syntax-Baum.</param>
        /// <returns>Der Knoten welcher in den Syntax-Baum eingegliedert werden muss</returns>
        private XmlElement ParseEbnfTerm(XmlDocument tree)
        {
            XmlElement term = tree.CreateElement("Term");

            // Pflicht-Faktor lesen
            term.AppendChild(ParseEbnfFactor(tree));

            // Weitere Faktoren lesen wenn vorhanden
            EbnfSymbol symbol = CurrentSymbol;
            bool multipleTerms = false;
            while (symbol.Value != "" && symbol.Value != "." && symbol.Value != "=" && symbol.Value != "|"
                && symbol.Value != ")" && symbol.Value != "]" && symbol.Value != "}")
            {
                term.AppendChild(ParseEbnfFactor(tree));
                symbol = CurrentSymbol;
                multipleTerms = true;
            }

            // Entweder Faktor-Liste oder Einzelfaktor anhängen
            return multipleTerms ? term : (XmlElement)term.RemoveChild(term.FirstChild);
        }

        /// <summary>
        /// Parst einen EBNF Faktor für den Syntax-Baum.
        /// </summary>
        /// <param name="tree">Der Syntax-Baum.</param>
        /// <returns>Der Knoten welcher in den Syntax-Baum eingegliedert werden muss</returns>
        private XmlElement ParseEbnfFactor(XmlDocument tree)
        {
            // Nächstes Symbol Prüfen
            EbnfSymbol symbol = NextSymbol;

            // Identifier oder Terminalsymbol
            if (symbol.Type == EbnfSymbolType.Identifier)
            {
                XmlElement identifier = tree.CreateElement("Identifier");
                identifier.SetAttribute("value", symbol.Value);
                return identifier;
            }
            if (symbol.Type == EbnfSymbolType.Literal || symbol.Type == EbnfSymbolType.Literal2)
            {
                XmlElement literal = tree.CreateElement("Terminal");
                literal.SetAttribute("value", RemoveQuotes(symbol.Value));
                return literal;
            }

            // Gruppierung 
            if (IsSymbol(symbol, EbnfSymbolType.Operator, "("))
            {
                // Unterausdruck parsen
                XmlElement expression = ParseEbnfExpression(tree);

                // Gruppierung auch geschlossen?
                symbol = NextSymbol;
                if (!IsSymbol(symbol, EbnfSymbolType.Operator, ")"))
                    throw new SyntaxException("')' als Gruppenende erwartet an Position: " + symbol.Position,
                                              symbol.Position);
                return expression;
            }
            // Optional
            if (IsSymbol(symbol, EbnfSymbolType.Operator, "["))
            {
                // Unterausdruck parsen
                XmlElement option = tree.CreateElement("Option");
                option.AppendChild(ParseEbnfExpression(tree));

                // Gruppierung auch geschlossen?
                symbol = NextSymbol;
                if (!IsSymbol(symbol, EbnfSymbolType.Operator, "]"))
                    throw new SyntaxException(
                        "']' als Ende einer optionalen Gruppe erwartet an Position: " + symbol.Position,
                        symbol.Position);
                return option;
            }
            // Wiederholung
            if (IsSymbol(symbol, EbnfSymbolType.Operator, "{"))
            {
                // Unterausdruck parsen
                XmlElement loop = tree.CreateElement("Loop");
                loop.AppendChild(ParseEbnfExpression(tree));

                // Gruppierung auch geschlossen?
                symbol = NextSymbol;
                if (!IsSymbol(symbol, EbnfSymbolType.Operator, "}"))
                    throw new SyntaxException("'}' als Ende einer Wiederholung erwartet an Position: " + symbol.Position,
                                            symbol.Position);
                return loop;
            }

            // Kein Faktor!
            throw new SyntaxException("Faktor erwartet an Position: " + symbol.Position, symbol.Position);
        }


        /// <summary>
        /// Prüft ob das gegebene Symbol einem Symbol mit den gegebenen Bedingungen entspricht.
        /// </summary>
        /// <param name="symbol">Das Symbol welches geprüft werden soll.</param>
        /// <param name="type">Der Typ welcher das Symbol haben soll.</param>
        /// <param name="value">Der Wert welcher das Symbol beinhalten soll..</param>
        /// <returns>
        /// 	<c>true</c> wenn das gegebene Symbol die Bedingungen erfüllt; andernfalls, <c>false</c>.
        /// </returns>
        private static bool IsSymbol(EbnfSymbol symbol, EbnfSymbolType type, string value)
        {
            return symbol.Type == type && symbol.Value == value;
        }

        private static string RemoveQuotes(string quotedString)
        {
            return quotedString.Substring(1, quotedString.Length - 2);
        }


        #endregion

        #region 3. Semantischer Auswerter

        /// <summary>
        /// Wertet den gegebenen Knoten aus dem Syntax-Baum semantisch aus. 
        /// D.h. es wird eine grafische Darstellung des Knoten gezeichnet.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <param name="leftToRight">Legt fest ob von links nach rechts gezeichnet wird (verwendet bei Schleifen)</param>
        /// <returns>Ein gerendertes Teilbild.</returns>
        private Image SemanticEvaluation(XmlElement node, bool leftToRight)
        {
            // Faktoren zuerst das keine beinflussung durch leftToRight
            // Dann Schleifen um die Pfeile von den Folgeelementen richtig zu zeichnen 

            switch (node.Name)
            {
                case "Identifier":
                case "Terminal":
                    return EvaluateFactor(node);
                case "Option":
                case "Loop":
                    return EvaluateGroups(node, leftToRight);
                case "Term":
                    return EvaluateTerm(node, leftToRight);
                case "Expression":
                    return EvaluateExpression(node, leftToRight);
                case "Syntax":
                    return EvaluateRoot(node, leftToRight);
                default:
                    return null;
            }
        }

        /// <summary>
        /// Verarbeitet den Root-Knoten des Syntax-Baumes.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <param name="leftToRight">Legt fest ob von links nach rechts gezeichnet wird (verwendet bei Schleifen)</param>
        /// <returns>Das gerenderte Gesamtbild.</returns>
        private Bitmap EvaluateRoot(XmlElement node, bool leftToRight)
        {
            string title = Error == null ? Title : "Fehler: " + Error.Message;
            Brush titleBrush = Error == null ? Brushes.Green : Brushes.Red;
            Pen borderPen = Error == null ? Pens.Green : Pens.Red;
            string[] names = new string[node.ChildNodes.Count];
            Image[] images = new Image[node.ChildNodes.Count];

            // Alle Sub-Elemente Rendern
            node = (XmlElement)node.FirstChild;
            int i = 0;
            while (node != null)
            {
                names[i] = node.GetAttribute("name");
                images[i] = SemanticEvaluation((XmlElement)node.FirstChild, leftToRight);
                node = (XmlElement)node.NextSibling;
                i++;
            }

            // Koordinaten für Bilder/Namen berechnen 
            int widthNames = 0;
            int widthImages = 0;
            int h = 5 * DrawingUnit;
            for (int j = 0; j < images.Length; j++)
            {
                widthNames = Math.Max(widthNames, TextRenderer.MeasureText(names[j], DefaultFont).Width);
                widthImages = Math.Max(widthImages, images[j].Width);
                h += images[j].Height + 2 * DrawingUnit;
            }
            if (string.IsNullOrEmpty(title))
            {
                h -= 2 * DrawingUnit;
            }


            Size fs = TextRenderer.MeasureText(title, DefaultFont);
            int w = Math.Max(widthImages + widthNames + 3 * DrawingUnit, fs.Width + 2 * DrawingUnit);

            Bitmap im = new Bitmap(w, h);
            Graphics g = CreateGraphics(im);
            int y = 2 * DrawingUnit;

            // Titel Zeichnen
            if (!string.IsNullOrEmpty(title))
            {
                g.DrawString(title, DefaultFont, titleBrush, DrawingUnit, (2 * DrawingUnit - fs.Height) / 2);
                g.DrawLine(borderPen, 0, 2 * DrawingUnit, w, 2 * DrawingUnit);
                y += 2 * DrawingUnit;
            }

            // Teilbilder inklusive Linien zeichnen
            for (int j = 0; j < images.Length; j++)
            {
                g.DrawString(names[j], DefaultFont, Brushes.Red, DrawingUnit, y - DrawingUnit + (DrawingUnit - fs.Height) / 2);
                g.DrawImage(images[j], widthNames + 2 * DrawingUnit, y);
                g.DrawLine(Pens.Black, DrawingUnit, y + DrawingUnit, widthNames + 2 * DrawingUnit, y + DrawingUnit);
                g.DrawLine(Pens.Black, widthNames + 2 * DrawingUnit + images[j].Width - 1, y + DrawingUnit, w - DrawingUnit, y + DrawingUnit);
                g.DrawLine(Pens.Black, w - DrawingUnit, y + DrawingUnit / 2, w - DrawingUnit, (int)(y + 1.5 * DrawingUnit));
                y += 2 * DrawingUnit + images[j].Height;
            }

            // Dekorativer Rahmen
            DrawRoundRect(g, 0, 0, w - 1, h - 1, DrawingUnit / 2, borderPen);
            g.Dispose();
            return im;
        }

        /// <summary>
        /// Verarbeitet einen Term-Knoten des Syntax-Baumes.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <param name="leftToRight">Legt fest ob von links nach rechts gezeichnet wird (verwendet bei Schleifen)</param>
        /// <returns>Das gerenderte Teilbild.</returns>
        private Bitmap EvaluateTerm(XmlElement node, bool leftToRight)
        {
            // Unterknoten Zeichnen
            Image[] inner = EvaluateChilds(node, leftToRight);
            if (!leftToRight)
                Array.Reverse(inner);

            // Breite und Höhe des Teilbildes Berechnen
            int w = inner.Length * DrawingUnit - DrawingUnit;
            int h = 0;
            foreach (Image img in inner)
            {
                w += img.Width;
                h = Math.Max(h, img.Height);
            }

            // Alle Teilbilder der Unterknoten Zeichnen
            Bitmap im = new Bitmap(w, h);
            Graphics g = CreateGraphics(im);
            g.DrawImage(inner[0], 0, 0);

            int x = inner[0].Width + DrawingUnit;
            for (int i = 1; i < inner.Length; i++)
            {
                g.DrawLine(Pens.Black, x - DrawingUnit - 1, DrawingUnit, x, DrawingUnit);
                DrawArrow(g, x, DrawingUnit, leftToRight);
                g.DrawImage(inner[i], x, 0);
                x += inner[i].Width + DrawingUnit;
            }
            g.Dispose();
            return im;
        }

        /// <summary>
        /// Verarbeitet einen Faktor-Knoten des Syntax-Baumes.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <returns>Das gerenderte Teilbild.</returns>
        private Bitmap EvaluateFactor(XmlElement node)
        {
            // Textmaße berechnen
            string text = node.GetAttribute("value");
            SizeF fs = TextRenderer.MeasureText(text, DefaultFont);
            float w = fs.Width + 4 * DrawingUnit;
            float fh = fs.Height;
            float h = 2 * DrawingUnit;

            Bitmap im = new Bitmap((int)w, (int)h);
            Graphics g = CreateGraphics(im);
            // Terminale ohne Rundung
            if (node.Name != "Terminal")
            {
                g.DrawRectangle(Pens.Black, DrawingUnit, 0, w - (2 * DrawingUnit) - 1, h - 1);
                g.DrawString(text, DefaultFont, Brushes.Red, 2 * DrawingUnit, (h - fh) / 2);
            }
            // Identifier mit Rundung
            else
            {
                if (text != "...")
                    DrawRoundRect(g, DrawingUnit, 0, w - DrawingUnit - 1, h - 1, DrawingUnit / 2, Pens.Black);
                g.DrawString(text, DefaultFont, text != "..." ? Brushes.Blue : Brushes.Black, 2 * DrawingUnit,
                             (h - fh) / 2);
            }

            g.DrawLine(Pens.Black, 0, DrawingUnit, DrawingUnit, DrawingUnit);
            g.DrawLine(Pens.Black, w - DrawingUnit, DrawingUnit, w + 1, DrawingUnit);
            g.Dispose();
            return im;
        }

        /// <summary>
        /// Verarbeitet einen Ausdrucks-Knoten des Syntax-Baumes.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <param name="leftToRight">Legt fest ob von links nach rechts gezeichnet wird (verwendet bei Schleifen)</param>
        /// <returns>Das gerenderte Teilbild.</returns>
        private Bitmap EvaluateExpression(XmlElement node, bool leftToRight)
        {
            // Terme Zeichnen
            Image[] inner = EvaluateChilds(node, leftToRight);

            // Teilbildgröße berechnen
            int h = (inner.Length - 1) * DrawingUnit;
            int w = 0;
            foreach (Image img in inner)
            {
                h += img.Height;
                w = Math.Max(w, img.Width);
            }
            w += 6 * DrawingUnit;

            // Teilbilder inklusive Pfeile berechnen
            Bitmap im = new Bitmap(w, h);
            Graphics g = CreateGraphics(im);
            int y = 0;
            int top = 0;
            g.DrawLine(Pens.Black, 0, DrawingUnit, DrawingUnit, DrawingUnit);
            g.DrawLine(Pens.Black, w - DrawingUnit, DrawingUnit, w, DrawingUnit);
            for (int i = 0; i < inner.Length; i++)
            {
                g.DrawLine(Pens.Black, DrawingUnit, y + DrawingUnit, w - DrawingUnit, y + DrawingUnit);
                g.DrawImage(inner[i], 3 * DrawingUnit, y);
                DrawArrow(g, 3 * DrawingUnit, y + DrawingUnit, leftToRight);
                DrawArrow(g, w - 2 * DrawingUnit, y + DrawingUnit, leftToRight);
                top = y + DrawingUnit;
                y += inner[i].Height + DrawingUnit;
            }
            g.DrawLine(Pens.Black, DrawingUnit, DrawingUnit, DrawingUnit, top);
            g.DrawLine(Pens.Black, w - DrawingUnit, DrawingUnit, w - DrawingUnit, top);
            g.Dispose();

            return im;
        }

        /// <summary>
        /// Verarbeitet einen Gruppen-Knoten (Schleife oder Optional) des Syntax-Baumes.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <param name="leftToRight">Legt fest ob von links nach rechts gezeichnet wird (verwendet bei Schleifen)</param>
        /// <returns>Das gerenderte Teilbild.</returns>
        private Bitmap EvaluateGroups(XmlElement node, bool leftToRight)
        {
            // Bei Schleifen die Reihenfolge umkehren
            if (node.Name == "Loop")
                leftToRight = !leftToRight;

            // Ausdruck in Gruppe auswerten. 
            Image inner = SemanticEvaluation((XmlElement)node.FirstChild, leftToRight);
            int w = inner.Width + 6 * DrawingUnit;
            int h = inner.Height + 2 * DrawingUnit;

            // Unterbild und Pfeile zeichnen
            Bitmap im = new Bitmap(w, h);
            Graphics g = CreateGraphics(im);

            g.DrawImage(inner, new Point(3 * DrawingUnit, 2 * DrawingUnit));
            g.DrawLine(Pens.Black, 0, DrawingUnit, w, DrawingUnit);
            DrawArrow(g, w / 2 + DrawingUnit / 2, DrawingUnit, node.Name == "Loop" ? !leftToRight : leftToRight);
            DrawArrow(g, 3 * DrawingUnit, 3 * DrawingUnit, leftToRight);
            DrawArrow(g, w - 2 * DrawingUnit, 3 * DrawingUnit, leftToRight);
            g.DrawLine(Pens.Black, DrawingUnit, DrawingUnit, DrawingUnit, DrawingUnit * 3);
            g.DrawLine(Pens.Black, DrawingUnit, 3 * DrawingUnit, 2 * DrawingUnit, 3 * DrawingUnit);
            g.DrawLine(Pens.Black, w - DrawingUnit, DrawingUnit, w - DrawingUnit, 3 * DrawingUnit);
            g.DrawLine(Pens.Black, w - 3 * DrawingUnit - 1, 3 * DrawingUnit, w - DrawingUnit, 3 * DrawingUnit);
            g.Dispose();

            return im;
        }

        /// <summary>
        /// Verarbeitet die Kinder eines Knotens des Syntax-Baumes.
        /// </summary>
        /// <param name="node">Der Knoten aus dem Syntax-Baum..</param>
        /// <param name="leftToRight">Legt fest ob von links nach rechts gezeichnet wird (verwendet bei Schleifen)</param>
        /// <returns>Die gerenderten Teilbild.</returns>
        private Image[] EvaluateChilds(XmlElement node, bool leftToRight)
        {
            Image[] childs = new Image[node.ChildNodes.Count];
            node = (XmlElement)node.FirstChild;
            int i = 0;
            while (node != null)
            {
                childs[i] = SemanticEvaluation(node, leftToRight);
                node = (XmlElement)node.NextSibling;
                i++;
            }
            return childs;
        }

        #region Zeichenhelfer

        /// <summary>
        /// Erzeugt ein Grafikobjekt für das Zeichnen aufbasis eines Bilders. 
        /// </summary>
        /// <param name="img">Das Bild in welches gezeichnet wird..</param>
        /// <returns>Das Grafikobjekt welches zum Zeichnen in das Bild verwenden kann.</returns>
        private static Graphics CreateGraphics(Image img)
        {
            Graphics g = Graphics.FromImage(img);
            g.Clear(Color.White);
            g.TextRenderingHint = TextRenderingHint.ClearTypeGridFit;
            g.SmoothingMode = SmoothingMode.HighQuality;
            return g;
        }

        /// <summary>
        /// Zeichnet eine Pfeilspitze.
        /// </summary>
        /// <param name="g">Das Grafikobjekt in welches gezeichnet wird..</param>
        /// <param name="x">Die x Position.</param>
        /// <param name="y">Die y Position.</param>
        /// <param name="leftToRight">true wenn der Pfeil von links nach rechts zeigen soll, andernfalls false</param>
        private static void DrawArrow(Graphics g, int x, int y, bool leftToRight)
        {
            Point[] points = !leftToRight
                                 ? new[] { new Point(x, y - DrawingUnit / 3), new Point(x - DrawingUnit, y), new Point(x, y + DrawingUnit / 3) }
                                 : new[] { new Point(x - DrawingUnit, y - DrawingUnit / 3), new Point(x, y), new Point(x - DrawingUnit, y + DrawingUnit / 3) };

            g.FillPolygon(Brushes.Black, points);
        }

        /// <summary>
        /// Zeichnet ein rundes Rechteck in den gegebenen Bereich.
        /// </summary>
        /// <param name="g">Die Grafik in welche gezeichnet wird.</param>
        /// <param name="x1">Die Anfangs-X-Position des Rechtecks</param>
        /// <param name="y1">Die Anfangs-Y-Position des Rechtecks</param>
        /// <param name="x2">Die End-X-Position des Rechtecks</param>
        /// <param name="y2">Die End-Y-Position des Rechtecks</param>
        /// <param name="r">Der Radius der Runding.</param>
        /// <param name="pen">Der verwendete Stift für das Zeichnen.</param>
        private static void DrawRoundRect(Graphics g, float x1, float y1, float x2, float y2, float r, Pen pen)
        {
            g.DrawLine(pen, x1 + r, y1, x2 - r, y1);
            g.DrawLine(pen, x1 + r, y2, x2 - r, y2);
            g.DrawLine(pen, x1, y1 + r, x1, y2 - r);
            g.DrawLine(pen, x2, y1 + r, x2, y2 - r);
            g.DrawArc(pen, x1, y1, 2 * r, 2 * r, 180, 90);
            g.DrawArc(pen, x2 - (2 * r), y1, 2 * r, 2 * r, 270, 90);
            g.DrawArc(pen, x1, y2 - (2 * r), 2 * r, 2 * r, 90, 90);
            g.DrawArc(pen, x2 - (2 * r), y2 - (2 * r), 2 * r, 2 * r, 0, 90);
        }

        #endregion

        #endregion
    }
}